/**
 * describe:
 *
 * @author chaP
 * @date 2018/12/27
 */
package CodingTest;

/**
 * 实现 int sqrt(int x) 函数。

 计算并返回 x 的平方根，其中 x 是非负整数。

 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

 示例 1:

 输入: 4
 输出: 2
 示例 2:

 输入: 8
 输出: 2
 说明: 8 的平方根是 2.82842...,
 由于返回类型是整数，小数部分将被舍去。
 */
public class mySqrt {
    public int mySqrt(int x) {
        if(x == 0)
            return 0;
        int i;
    //我一开始错误的写法：i * i <= x && （i+1）* (i+1) > x。这样会导致溢出。应该如下写成除法！
        for(i =1;i<=(x/2)+1;i++){
            if(x / i >= i && x/(i+1) < (i+1))
                break;
        }

        return i;
    }
    public static void main(String[] args){
        mySqrt ms = new mySqrt();
        int h = ms.mySqrt(2147395600);
        System.out.print(h);
    }
}
